SCCPC2026 J 献给空白的无败冠冕 题解

题目链接：QOJ Contest 3789 Problem J

棋盘只有两行，因此一条路径完全由下移列 决定。题目要我们填出一个棋盘，使得“白让自己拿到最多硬币”的策略会唯一地选择某条路径，但这条路径并不是让空收益最小的正确选择。

先把真正影响路径比较的格子提出来。无论白选择哪条路径，左上角 和右下角 都一定会被经过，所以它们不会影响路径之间的优劣。相邻两条路径的差别只来自每两列之间的一对斜对角格子，记

若原格子已经给定，对应变量的上下界相等；若原格子为 ，上下界就是 。记为

白选择下移列 后，没有被白拿走的部分分成上方剩余和下方剩余两段：

空会选择自己能拿到更多的一边，所以白真正应该最小化的是

但错误策略是让白自己拿到最多硬币。设棋盘总和为 ，白选择 时拿到 ，所以错误策略等价于最小化

我们要构造的就是这样一种局面： 有唯一最小点 ，但 不是 的最小点。

先刻画“ 唯一最小”。相邻两条路径满足

因此

若 是唯一最小，那么从 往左或往右走， 都必须严格变大。写成条件就是

以及

也就是说， 左边所有后缀和为正， 右边所有前缀和为正。

接着看怎样让这个唯一选择变成错误选择。假设白唯一选择了 。如果 ，空在路径 下主要拿上方剩余部分；这时把下移列向右挪，会减少上方剩余、增加下方剩余。若某个更右的路径能让 变小，那么相邻的 已经能做到。左边的情况完全对称。因此只需要尝试两类构造：让 比 更优，或者让 比 更优。下面只描述右侧反例；左侧可以把序列反过来用同样的方法处理。

右侧反例要求 。由

可知，只要

就够了。展开后为

于是我们希望左边尽量大、右边尽量小，同时还要维持 唯一最小。

先处理 左边。为了让左侧所有后缀和尽量容易为正，并且让上式右边尽量小，取

令 $e_i=\mathrm{ux}_i-\mathrm{ly}ie_1,\ldots,e{p-1}$ 的所有后缀和都为正；若可行，上式右边能取到的最小值是

$$
\mathrm{leftMinY}p=\sum{i=1}^{p-1}\mathrm{ly}_i.
$$

后缀和是否全为正可以线性预处理。设

则 ，只要 ，左侧就可行。

再看中心位置 。为了让 右边的 一开始严格上升，需要 。记

它必须满足

我们会取满足所有条件的最小 ，因为这样留给右半边的限制最宽松。

对 ，为了让右侧反例的不等式左边尽量大，先取 ，再令 。于是

其中

右侧所有前缀和为正等价于

记

$$
\mathrm{need}p=\max\left(0,\max{t>p}\sum_{i=p+1}^{t}L_i\right).
$$

那么为了让右半边至少有解，必须让 。综合中心位置的上下界，最小可行的

如果这个值超过 ，当前 就不可能作为右侧反例中心。

确定 后，设 。右半边还要在所有前缀和不超过 的条件下最大化 。这个最大值为

$$
\mathrm{best}p=
\min\left(
\sum{i=p+1}^{n-1}U_i,
C+\min_{q\ge p+2}\sum_{i=q}^{n-1}U_i
\right).
$$

可以理解成：如果全取上界不会出问题，就全取上界；否则某个前缀会先被 卡住，之后的后缀继续尽量取上界。这个式子可以用 的后缀和与后缀最小值 求出。

于是右侧不等式左边能达到的最大值是

$$
\mathrm{maxRight}p=-z+\sum{i=p+1}^{n-1}\mathrm{uy}_i+\mathrm{best}_p.
$$

右侧反例存在，当且仅当左半边可行，并且

这些量都能通过前缀和、后缀和、最大前缀下界、后缀最小值在线性时间内预处理，因此可以枚举每个 判断。

找到可行的 后，构造也沿用判定时的取法。左边取 ；中心选一组满足 且在上下界内的 ；右边固定 ，再构造 。

构造 时，需要满足 ，并且所有前缀和不超过 。可以先从左到右算每个前缀和的最小可能值 ，再算最大可能值 并用 截断，最后从最终前缀和倒推。若当前前缀和为 ，正在倒推第 个变量，则上一个前缀和 需要落在

中。任选一个合法的 ，令 即可。判定阶段已经保证可行，所以这个倒推一定能成功。

如果右侧反例找不到，就对称地尝试左侧反例；两边都找不到则输出 。最后把构造出的变量还原成棋盘：

没有参与变量的 和 不影响路径选择，若原本是 ，填 即可，否则保留原值。

总时间复杂度为 ，空间复杂度为 。